package study.数据结构.线性结构.递归;

/*
    递归回溯说明：
        递归回溯底层运行的形式是像栈一样，它不断的调用自己(当进入递归后，递归下面的代码将先暂停，
        直到开始回溯后，再开始执行)，不断地往栈中添加方法，直到栈顶出现了一个方法满足了
        递归头（此时开始回溯），开始返回栈顶的下一层，继续执行调用自己的代码的下面的代码，
        执行完后再返回上上层，以此类推
 */
public class Queue8 {

    //定义一个max表示共有多少个皇后
    int max = 8;
    //定义数组array，保存皇后放置位置的结果
    int arr[] = new int[max];
    static int count = 0;
    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.printf("一共有%d解法",count);
    }

    //写一个方法,将皇后摆放的位置输出
    private void print() {
        count++;
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    /**
     * @param n 表示放第N个皇后
     * @return 是否冲突
     */
    //查看放置的皇后，是否和前面已经摆放的皇后冲突
    private boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            //Math.abs(n - i) == Math.abs(arr[n] - arr[i])
            //Math.abs(n - i)相当于宽    Math.abs(arr[n] - arr[i])相当于长
            //当宽=长时，表明这两个皇后在这个矩形的对角线上（即在同一斜线上）
            if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) {
                return false;   //冲突
            }
        }
        return true;  //不冲突
    }

    //编写一个方法，放置第n个皇后
    private void check(int n) {
        if (n == max) {  //n=8  相当于放第9个皇后了，超过了，每必要再放了
            print();
            return;
        }

        //没有放完，依次放入皇后，并判断是否冲突
        for (int i = 0; i < 8; i++) {   //这里用8是因为棋盘只有8列
            //把皇后依次放入i列
            arr[n] = i;
            //判断当放置第n个皇后放到i列时，是否与之前放入的皇后冲突
            if (judge(n)) {  //当judge方法返回true时表示  不冲突
                //接着放n+1个皇后，即开始递归
                check(n + 1);
            }
            //if外表示皇后有冲突，那么就会进行下一次循环，将i++ 去重复操作
        }
    }
}
